package _02_linked_list.exerc.remove;

import _02_linked_list.exerc.ListNode;
import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 7:04
 * 删除链表中的倒数第 n 个节点 1 <= n <= size
 */
public class MyTest2 {
    @Test
    public void test() {
        ListNode list = MyTest.init(new int[]{1,2,3});
        System.out.println(list);

//        System.out.println(foo1(list, 3));
        System.out.println(foo4(list, 3));
//        System.out.println(foo3(list, 3));
    }

    /**
     * 方式1 递归删除
     */
    ListNode foo1(ListNode listNode, int n) {
        ListNode s = new ListNode();
        s.next = listNode;
        foo1_1(s, n);
        return s.next;
    }

    private int foo1_1(ListNode list, int n) {
        if (list == null) {
            return 0;
        }
        int i = foo1_1(list.next, n);
        if(i == n) {
            list.next = list.next.next;
        }
        return i + 1;
    }

    /**
     * 方式4 双指针
     * @param listNode
     * @param n
     * @return
     */
    ListNode foo4(ListNode listNode, int n) {
        ListNode s = new ListNode();
        s.next = listNode;
        ListNode p1 = s;
        ListNode p2 = s;
        for (int i = 0; i <= n; i++) {
            p1 = p1.next;
        }

        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        return s.next;
    }

    /**
     * 方式2 leetcode 官方
     * @param head 头节点
     * @param n 要删除元素的倒数下标
     * @return
     */
    ListNode foo2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            // 等价于 addFirst(e) 添加头节点
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            // 弹出 first 节点
            stack.pop();
        }
        // peek 查看 first 节点的值
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    // 方式3
    ListNode foo3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}
